package praktikum_3_ylesanded.ylesanne_1;

/**
 * Created by IntelliJ IDEA.
 * User: Jaan
 * Date: 17.11.11
 * Time: 22:20
 */
public class PriorityQueue {

  DynamicArray dynamicArray;
  int currentIndex;
  int rootNodeIndex;

  public PriorityQueue() {
    dynamicArray = new DynamicArray();
    dynamicArray.add(new Node());
    currentIndex = 1;
    rootNodeIndex = 0;
  }


  //Exchanges the values of two nodes.
  private void exchange(int newNodeIndex, int parentNodeIndex) {
    Node tempNodeValue = dynamicArray.get(parentNodeIndex);
    dynamicArray.put(dynamicArray.get(newNodeIndex), parentNodeIndex);
    dynamicArray.put(tempNodeValue, newNodeIndex);
  }

  //Adds a new node and then reorganizes the priorityqueue, if necessary.
  public void enqueue(Node newValue) {
    dynamicArray.add(newValue);
    int nextCurrentIndex = currentIndex + 1;
    int parentIndex = currentIndex / 2;
    while (parentIndex != rootNodeIndex && dynamicArray.get(parentIndex).weight > newValue.weight) {
      exchange(parentIndex, currentIndex);
      currentIndex = parentIndex;
      parentIndex = parentIndex / 2;
    }
    currentIndex = nextCurrentIndex;
  }

  //If the length of the array is smaller than 2 then the priorityqueue is empty.
  public boolean isEmpty() {
    return (dynamicArray.len() < 2);
  }

  public Node[] getDynamicArray() {
    return dynamicArray.getDynamicArray();
  }

  public int getCurrent() {
    return currentIndex;
  }

  public Node dequeue() {
    Node out = dynamicArray.getDynamicArray()[1];
    dynamicArray.put(null, 1); //TODO: null is OK?
    currentIndex-- ;
    exchange(currentIndex, 1);
    dynamicArray.rem();
    int parentIndex = 1;


    //Logic for finding the first smallest child.
    int smallerChildIndex;
    smallerChildIndex = getSmallestChild();

    while(smallerChildExists(parentIndex, smallerChildIndex) && dynamicArray.get(parentIndex).weight > dynamicArray.get(smallerChildIndex).weight) {
      exchange(parentIndex, smallerChildIndex);
      parentIndex = smallerChildIndex;
      smallerChildIndex = (dynamicArray.get(parentIndex * 2).weight < dynamicArray.get(parentIndex*2 + 1).weight ? parentIndex * 2 : parentIndex * 2 + 1);
    }
    return out;
  }

  //Check if the rootnode has any childnodes.
  private int getSmallestChild() {
    int smallerChildIndex;
    if(dynamicArray.len() == 3){
      if(dynamicArray.len() == 2) {
        smallerChildIndex = 0;
      }
      else {
        smallerChildIndex = 2;
      }
    }
    else{
      smallerChildIndex = dynamicArray.get(2).weight < dynamicArray.get(3).weight ? 2 : 3;
    }
    return smallerChildIndex;
  }

  //Checks if the parent has any children.
  private boolean smallerChildExists(int parentIndex, int smallerChildIndex) {
    return !((parentIndex * 2) > currentIndex + 1) && (dynamicArray.len() > smallerChildIndex);
  }
}
